package leetcode.editor.day;

// 670. 最大交换
// https://leetcode.cn/problems/maximum-swap/
class MaximumSwap {
    public static void main(String[] args) {
        Solution solution = new MaximumSwap().new Solution();
//        solution.maximumSwap(2736);
        solution.maximumSwap(43265);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 数据较小，暴力
        // 每个数都进行交换来比较
        /*public int maximumSwap(int num) {
            char[] arr = String.valueOf(num).toCharArray();
            int res = num;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    swap(arr, i, j);
                    res = Math.max(res, Integer.parseInt(new String(arr)));
                    swap(arr, i, j);
                }
            }

            return res;
        }

        public void swap(char[] arr, int i, int j) {
            char c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
        }*/

        // 贪心
        // 每一位数字都应该大于后面的数字，如果小于，那么就找到最后一位最大值进行交换
        public int maximumSwap(int num) {
            char[] arr = String.valueOf(num).toCharArray();
            int idx1 = -1, idx2 = -1, maxIdx = arr.length - 1;
            // 一直找到最左边的，和最右边的最大值交换
            // 例如：43265 -> 63245
            for (int i = arr.length - 1; i >= 0; i--) {
                if (arr[i] > arr[maxIdx]) {
                    maxIdx = i;
                } else if (arr[i] < arr[maxIdx]) {
                    // 记录交换索引，注意不修改maxIdx，因为此时就是右边最大的索引
                    idx1 = i;
                    idx2 = maxIdx;
                }
            }

            if (idx1 >= 0) {
                swap(arr, idx1, idx2);
                return Integer.parseInt(new String(arr));
            } else {
                // 不用交换
                return num;
            }
        }

        public void swap(char[] arr, int i, int j) {
            char c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
